Hallo zusammen. Ich bin nicht Dominik Schröder wie ihr seht, sondern in der gleichen Gruppe zählt

Mein Name ist Paul Röschler. Ich spam immer das Professor. Ich arbeite in der gleichen Gruppe und kümmere mich auch um

Gruppografie. Meine Gruppe heißt Real World Crypto. Warum ich mich im Wesentliche kümmere ist sichere Messenger. Also so

war es wie WhatsApp. Ich schaue mir an, ob die Protokolle, die da verwendet werden, zur Verschlüsselung sicher sind. Das tut nicht

wirklich was zur Sache hier in dieser Grundlagenvorlesung. Aber falls ihr irgendwann mal genau über diese Grundlagenvorlesung hinauskommt,

euch eine Bachelor in Arbeit interessiert in diesem Gebiet, dann könnt ihr euch gerne bei mir melden. Genau, ich schaue mir im Wesentlichen an, wie man Messaging Protokolle sicher macht, wie man das in

Gruppen hinbekommen, wie man das ganz effizient hinbekommen, wie man Traders zwischen Effizienz und Sicherheit hinbekommen. Und da kommen auch gleich schon zum Thema.

Ich finde, dass wir hier in der Nähe sind. Viele solcher Effizienzfragen lassen sich beantworten mit Grafen-Theorie. Also mit der Frage, die man dann runterbricht auf Grafen. Ihr kennt sicherlich Grafen vielleicht auch noch aus der Schule. Und wir werden uns heute im Wesentlichen leider sehr trocken,

wie man mit Grafen arbeitet, was Grafen sind. Ich habe, als ich vorhin vom Hörsal gesessen habe, kurz das Gespräch mitbekommen, ohne dass ich weiß, wer es gesagt habe, weil ich die Leute nicht gesehen, aber die Frage war, ob Mathe oder die Algorithmenfallesung schlimmer ist und es gab beide Meinungen.

Ich versuch es für euch so einfach und so nachvollziehbar, wie möglich heute zu machen. Aber bei Grundlagenfallesung hat man leider manchmal eben als Studie keine Wahl. Es ist aber trotzdem wahnsinnig wichtig. Egal, was für eine Karriere ihr anstrebt, später, ob ihr irgendwie eine Industrie geht oder an der Uni bleibt, gerade diese Grundlagen Dinge, wie letzte Woche Sortieralgerhythmen und diese Woche Grafen-Theorie sind wahnsinnig wichtig im Hinterkopf zu behalten.

Weil sie sind letztlich überall eine mögliche Weg, ein Antwort für Probleme zu finden. Genau, also was war vorletzte Woche?

Was war letzte Vorlesung des Thema? Die letzte Vorlesung ging es um Sortieralgerhythmen und heute geht es um Grafen.

Wenn ihr Fragen habt, den ihr was nicht lesen könnt, ich versuche eigentlich alles, was ich aufschreibe zu erzählen, das heißt grundsätzlich soll es eine gewisse Redundanz geben. Oder wenn irgendwas euch komisch vorkommt, weil ich es anders mache als Professor Schröder, dann sagt mir das auch gerne, wir haben uns saabgesprochen, aber wir haben uns jetzt nicht ganz im Detail erzählt, wie genau jetzt jeder die Vorlesung hält.

Also falls ihr irgendwas vermisst oder so sagt mir gerne Bescheid, genau einfach aufzeigen, wenn ich euch nicht sehr reinrufen, Grafen. Es geht heute um Grafen.

Ein der bekanntesten Kindergartenprobleme, das ihr kennt, das man mit Grafen lösen kann, das letztlich auch ein Grafenproblem ist, ist das Haus zum Nikolaus. Die Frage kriegt man das Haus zum Nikolaus in einem Fahrt gezeichnet und vielleicht auch die zweite Frage dazu kriegt man es hin, dass Start und Endknoten die gleichen sind.

Sicherlich kennt ihr alle die Antwort, aber Grafen Theorie hilft einem eben das Ganze auch für komplexere Häuser vom Nikolaus als ein zweidimensionales Fachwerk, ähnliches Haus zum Malen.

Also das Haus zum Nikolaus hat eine Lösung, die ungefähr so aussieht.

Das ist das Haus von Nikolaus, wie ihr seht, es gibt eine Lösung, die Frage ist wie löst man das theoretisch möglicherweise kümmern wir uns darum in einer zukünftigen Vorlesung heute nicht wirklich.

Es geht erst mal nur um die Motivation und die Frage, wie ich gerade schon gesagt habe, ist zum einen Zeichenbar in einem Fahrt.

Frage zeichen und vielleicht auch die Frage Zeichenbar in einem Fahrt mit Startgleichende.

Das ist das erste Motivierende Beispiel. Das zweite Motivierende Beispiel ist auch ein ganz bekannte Beispiel, dass man in der Grafen Theorie sich anschaut.

Ich weiß nicht, stehe hier so halb und sitze, so halb nicht, wie macht Dominik Schröder das? Der steht ja, der steht, okay, bückt sich auch so komisch.

Alles klar.

Das zweite interessante Beispiel ist die sogenannte Städtatur mit der Frage, sagen wir beispielsweise, wir haben hier Erlang, dann haben wir hier Berlin,

wir München, hier Frankfurt, keine Ahnung, hier Paris. Die Frage ist, sicherlich gibt es natürlich zwischen all diesen Ständen irgendeine Verbindung.

Die Frage ist, man kann das jetzt noch vollständig malen, indem man von Paris an ein Weg hierhin macht und von Berlin auch ein Weg nach Paris. Irgendwelche Auszubahnen gibt es zwischen diesen ganzen Städten.

Das erste Frage ist, kriegen wir Sinn, eine Städtatur zu machen von einer Stadt, stattend, über alle anderen Städte, geht bis zum Ende wieder der, genau, bei der Ende der Anfälle gleichzeitig auch der Anfang sein soll.

Wie Sie Frage ist, kann man sich zum Beispiel vorstellen mit dem Euro-Ticket, mit Bahnenlinien, ohne dass man beispielsweise auch Kanten mehrfach verwendet, also dass man mehrfach für die gleiche Bahnenlinie fährt, kriegt man es Sinn, dass man jede Städt nur genau einmal besucht, ohne dass man mehrfach an einer Stadt ankommt.

Uns gerade beim Haus vom Nikolaus gesehen, so, wie wir das gezeichnet haben, sind wir an mehreren der Knoten mehrfach angekommen, also, beispielsweise letztlich, alle bis auf der ganz oberen Topknoten in diesem Graf wurde mehrfach besucht.

Genau, bei der Städtatur ist die Frage, kriegt man das eben hin, diese Städtatur zu machen, ohne dass man mehrfach in der gleichen Stadt landen muss.

Möglichst wenig Verbindung und Startlachende.

Genau, dann kann man sich natürlich auch noch vorstellen. Und tatsächlich ist das der wesentliche Anwendungszweck für Grafen, wenn man es ganz plastisch darstellen möchte.

Ich möchte tatsächlich auch jedes Mal Frage, wie effizient das Ganze funktioniert oder wie tatsächlich das Ganze im Hintergrund implementiert wird. Google Maps ist das beste Beispiel dafür, wie Grafen eingesetzt werden und wie man den schnellsten Pfad finden kann von A nach B.

Und umso mehr Möglichkeiten, wenn man in Google Maps verwendet werden, umso mehr Standorte, umso mehr Wege, Google Maps findet, desto komplexer, wird die Suche nach dem schnellsten Weg von A nach B.

Genau, diese kürzeste, kürzeste, strecke, schnellste, strecke vor allen Dingen, also kürzeste, strecke und schnellste, strecke muss ja dabei auch nicht das Gleiche sein.

Da möchte man wenig Sprit verbrauchen, mit dem Auto oder es geht eben nur um Zeit und dann möchte man den schnellsten Weg und all diese Probleme sind letztlich, genau, das kürzeste, strecke, problem oder kürzeste, wege, problem.

Genau, alles so.

Wie komme ich am schnellsten von A nach B?

B? Wenigste, Kanten?

Kürzeste, Kanten?

Genau, da sieht man eben bei diesem Beispiel auch, dass es nicht unbedingt darum geht, die geringste Zahl an Knoten zu haben, sondern das werdet ihr sicherlich in den zukünftigen Vorlesungen noch mitbekommen.

Es geht eben auch um gewichtete Grafen, also man kann diesen Kanten auch gewichtegeben, in diesem ganzen großen Grafen sagen, okay, diese Kante ist schwerer als eine andere, es ist eben länger als eine andere oder eben diese Bedeutung, also was die Gewichtung einer Kante ist.

In diesem Problem hier kann ganz viele verschiedene Ideen sein, beispielsweise eben Distanz, wenn man sich eine Fahrradroute vorstellt, kann man sich vorstellen, dass die Steigung die Gewichtung sein kann und dann durch die Steigung eine Höhereanstrengung hat beim Fahrradfahren, das sind verschiedene Probleme, die man mit Grafen lösen kann.

Und das Ziel in der Vorlesung und auch in der Übung dann ist, Alberitmen zu finden, um mit diesen Grafen zu arbeiten, also Algo.

All die Probleme, die ich jetzt gerade erzählt habe, zumindest wenn man sie so klein aufschreibt, sind sie recht einfach ersichtlich.

Das wird aber wie gerade schon gesagt, bei dem Beispiel Google Maps sehr schnell klar, dass das Ganze eben nicht mehr durch reines draufschauen löst bei ist.

Solche Probleme werden eben komplexer und deswegen werden wir uns verschiedene Algerippen angucken. Heute sind das erst mal nur teuregsampe.

Aber genau in der in zukünftigen Vorlesung in der Übung vielleicht auch werdet ihr verstehen, warum das genau betrachten von Grafen eben wichtig ist, um zu verstehen, wofür Grafen hilfreich sind.

Das habe ich sehr viel über Grafen erzählt, das erste, was wir jetzt mal machen sollten, ist eine Definition von Grafen aufzuschreiben.

Ein Graf besteht aus zwei Mengen, nämlich zum einen der Knotenmenge V für Vertex oder Vertices.